Backpropagation Through Time 課本筆記

1 Backpropagation Through Time 課本筆記

我最近在學習 RNN (Recurrent Neural Network)，我對於這個模型在做 Backpropagation 的流程有點困惑，找著找著就找到一個線上課本有寫這個內容 (課本內容連結)。

我這篇文章主要是要記錄整個做 Backpropagation 的流程，並且把做 偏微導數 的過程記錄下來。

1.1 Elman Network Backpropagation Through Time

一個 RNN 它基本的運作流程如下，它有很多變種，但我這邊先考慮下面這一種，這個 Network 叫做 Elman Network。

圖如下：

RNN_elman_network

數學定義如下： \(x\in\mathbb{R}^n,\, h_t\in\mathbb{R}^k,\, o_t\in\mathbb{R}^m,\,t\in\{1,...,T\}\) 另外有一個 \(h_0\) 為初始值。

Hidden layer 的 function 為 \(h_t=f(x_t,h_{t-1},W_h)\)

Output layer 的 function 為 \(o_t=g(h_t,W_o)\)

我們給一組 trianing data \(\{...,(x_t,y_t),...\}\) 裡頭的 \(y_t\) 是對應於 \(x_t\) 的正確 Output

放入 \(x_1,...,x_T\) 做計算會得到 \(\{...,(x_t,h_t,o_t),...\}\) 這一組 data。

我們的目標是將 loss function 降到最低, loss function:

\(L(x_1,...x_t, y_1,...,y_t, W_h, W_o)=\frac{1}{T}\sum_{t=1}^T\ell(y_y,o_t)\)

再來我們要做 Backpropagation, 那我們在乎的 gradient 是 \(\frac{\partial L}{\partial W_o}\) 及 \(\frac{\partial L}{\partial W_h}\)，下面是 \(\frac{\partial L}{\partial W_o}\)：

\[ \begin{aligned} \frac{\partial L}{\partial W_o} &= \sum_{t=1}^T \frac{\partial L}{\partial o_t}\frac{\partial o_t}{\partial W_o}\ \end{aligned} \]

再來是 \(\frac{\partial L}{\partial W_h}\)：

\[ \begin{aligned} \frac{\partial L}{\partial W_h} &= \sum_{t=1}^T \frac{\partial L}{\partial o_t}\frac{\partial o_t}{\partial h_t}\frac{\partial h_t}{\partial W_h} \end{aligned} \]

這部分算起來比較 tricky 的就是 \(\frac{\partial h_t}{\partial W_h}\)

\[ \begin{aligned} \frac{\partial h_t}{\partial W_h} &= \frac{\partial_{W_h}f(x_t, h_{t-1}, W_h)}{\partial W_h} + \frac{\partial_{h_{t-1}}f(x_t, h_{t-1}, W_h)}{\partial h_{t-1}}\frac{\partial_{h_{t-1}}}{\partial W_h} \end{aligned} \]

這裡的 \(\partial_{W_h}f(x_t, h_{t-1}, W_h)\) 是只專注於對 \(W_h\) 這項來做偏微分，然後 \(\partial_{h_{t-1}}f(x_t, h_{t-1}, W_h)\) 專注在 \(h_{t-1}\) 來做偏微分，這個結果是 from total derivative chain rule 來的，這個是可以根據 Jacobian matrix 來推導出來的。

那根據上面的式子，我們來假設幾個符號

\(a_t=\frac{\partial_{h_{t}}}{\partial W_h}\)

\(b_t=\frac{\partial_{W_h}f(x_t, h_{t-1}, W_h)}{\partial W_h}\)

\(c_t=\frac{\partial_{h_{t-1}}f(x_t, h_{t-1}, W_h)}{\partial h_{t-1}}\)

那我們就可以得到

\(a_t = b_t + c_t a_{t-1}\)

帶入 \(a_{t-1}, ..., a_1\) 可以得到 \(a_t = b_t + \sum_{i=1}^{t-1}b_i \prod_{j=i}^t c_j\)

那我們就可以得到

\(\frac{\partial_{h_{t}}}{\partial W_h}=\frac{\partial_{W_h}f(x_t, h_{t-1}, W_h)}{\partial W_h}+ \sum_{i=1}^{t-1} \frac{\partial_{W_h}f(x_i, h_{i-1}, W_h)}{\partial W_h} \prod_{j=i}^t \frac{\partial_{h_{j-1}}f(x_j, h_{j-1}, W_h)}{\partial h_{j-1}}\)

進而得到

\[ \begin{aligned} \frac{\partial L}{\partial W_h} &= \sum_{t=1}^T \frac{\partial L}{\partial o_t}\frac{\partial o_t}{\partial h_t}(\frac{\partial_{W_h}f(x_t, h_{t-1}, W_h)}{\partial W_h}+ \sum_{i=1}^{t-1} \frac{\partial_{W_h}f(x_i, h_{i-1}, W_h)}{\partial W_h} \prod_{j=i}^t \frac{\partial_{h_{j-1}}f(x_j, h_{j-1}, W_h)}{\partial h_{j-1}}) \end{aligned} \]

再來把兩個偏微分 \(\frac{\partial L}{\partial W_h}\), \(\frac{\partial L}{\partial W_o}\) 拿來做 gradient descent，式子如下：

\(W_o\leftarrow W_o-\eta \frac{\partial L}{\partial W_o}\)

\(W_h\leftarrow W_h-\eta \frac{\partial L}{\partial W_h}\)

來更新出新的 \(W_o\) 和 \(W_h\)。

從式子你可以發現這個更新會隨著 T 越大，往回算的時間就會越久，而且 gradients 會有 blow up 的狀況，甚至是小小的變動都有可能對 outcome 有很大的影響。它除了全算以外還有兩種可能的做法：

1. Truncate time steps: 固定一個 \(\tau\) steps 然後在那個點 terminate，其實就是在上面說的 \(a_t=b_t+c_ta_{t-1}\) 的部分在展開的時候將 \(a_{t-\tau}\) 設定成 0。這方法在 practice 的效果還不錯。
2. Randomized truncation: 隨機 truncate，每次往前 truncate 的數量都不一定，會根據隨機數來決定。

在實務上 2. 表現得比 1. 好，可能的原因有：

1. 實務上，即便只做固定的 truncate，也已經足夠捕捉需要的依賴關係。
2. 雖然使用更多步會讓梯度更精準，但隨機截斷帶來的梯度變異性反而抵消了這個優點。
3. 其實大部分希望模型只學習短期互動。

固定部署不只簡單穩定，還能避免模型太過依賴長期歷史，具有 regularization 的作用。

1.2 Example

我們將 activation function 設定成 identity mapping，然後我們不放入 bias term 讓函數更簡單。

我們的數學式子定義如下：

\(x_t\in \mathcal{R}^n, h_t\in\mathcal{R}^k, o_t\in\mathcal{R}^m, W_hx\in\mathcal{R}^{k\times n},W_{hh}\in\mathcal{R}^{k\times k}, W_{oh}\in\mathcal{R}^{m\times k}\)

\(h_t=W_{hx}x_t + W_{hh} h_{t-1}\), \(o_t=W_{oh}h_t\)

然後我們的 loss function 設定為 \(L=\frac{1}{T}\sum_{t=1}^T\ell(o_t,y_t)=\frac{1}{T}\sum_{t=1}^T||o_t-y_t||^2\)

那我們想算出的 gradient 為 \(\frac{\partial L}{\partial W_{hx}}, \frac{\partial L}{\partial W_{hh}}, \frac{\partial L}{\partial W_{oh}}\)

來先算簡單的 \(\frac{\partial L}{\partial W_{oh}}\)

\(\frac{\partial L}{\partial W_{oh}}=\sum_{t=1}^Tprod(\frac{\partial L}{\partial o_t}, \frac{\partial o_t}{\partial W_{oh}})\), where \(prod(\cdot,\cdot)\) 代表的是對兩個偏微分出來後的 tensor 做適度的調整後來得到最後的 tensor，因為在運算的過程中常常會有許多維度對應或者是降維的行為，以此函數可以省去不少計算時的符號複雜度。

\(\frac{\partial L}{\partial o_t}=\frac{2}{T}(o_t-y_t)^{transpose}\) 算出來是一個 \(1\times m\) 的 rank 1 tensor

\(\frac{\partial o_t}{\partial W_{oh}}=I_m\otimes h_t^{transpose}\) 算出來是一個 \(m\times(m\times k)\) 的 rank 3 tensor，\(\otimes\) 是 Kronecker Product

整理整理後就會發現可以得到下面的式子

\(\frac{\partial L}{\partial W_{oh}}=\sum_{t=1}^Tprod(\frac{\partial L}{\partial o_t}, \frac{\partial o_t}{\partial W_{oh}})=\sum_{t=1}^T \frac{2}{T}(o_t-y_t)h_t^{transpose}\)

再來要計算 \(\frac{\partial L}{\partial W_{hx}}, \frac{\partial L}{\partial W_{hh}}\) 這兩個，他們展開後如下

\(\frac{\partial L}{\partial W_{hx}}=\sum_{t=1}^Tprod(\frac{\partial L}{\partial h_t}, \frac{\partial h_t}{\partial W_{hx}})\)

\(\frac{\partial L}{\partial W_{hh}}=\sum_{t=1}^Tprod(\frac{\partial L}{\partial h_t}, \frac{\partial h_t}{\partial W_{hh}})\)

它們有個共同的 term 是 \(\frac{\partial L}{\partial h_t}\)，我們先算這個，這個也是最tricky 的部分

我們先計算在 \(t=T\) 的時候

\[ \begin{aligned} \frac{\partial L}{\partial h_T} &= prod(\frac{\partial L}{\partial o_t}, \frac{\partial o_t}{\partial h_t})\\ &=\frac{2}{T}(o_t-y_t)^{transpose}W_{oh} \end{aligned} \]

再來算一般狀況

\[ \begin{aligned} \frac{\partial L}{\partial h_t} &= \frac{\partial_{h_t}L}{\partial h_t} + prod(\frac{\partial L}{\partial h_{t+1}}, \frac{\partial h_{t+1}}{\partial h_t})\\ &=prod(\frac{\partial L}{\partial o_{t}}, \frac{\partial o_{t}}{\partial h_t}) + prod(\frac{\partial L}{\partial h_{t+1}}, \frac{\partial h_{t+1}}{\partial h_t})\\ &=\frac{2}{T}(o_t-y_t)^{transpose}W_{oh} + \frac{\partial L}{\partial h_{t+1}}W_{hh} \end{aligned} \]

假設

\(a_t=\frac{\partial L}{\partial h_t}\)

\(b_t=\frac{2}{T}(o_t-y_t)^{transpose}W_{oh}\)

則 \[ \begin{aligned} a_t&=b_t+a_{t-1}W_{hh}\\ &=b_t+(b_{t-1}+(b_{t-2}+(...)W_{hh})W_{hh})W_{hh}\\ &=b_TW_{hh}^{T-t}+b_{T-1}W_{hh}^{T-(t+1)}+...+b_t \\ &= \sum_{i=t}^Tb_{T+t-i}W_{hh}^{T-i} \end{aligned} \]

所以我們可以得到

\(\frac{\partial L}{\partial h_t}=\sum_{i=t}^T\frac{2}{T}(o_{T+t-i}-y_{T+t-i})^{transpose}W_{oh}W_{hh}^{T-i}\)

再將剛算出來的代入 \[ \begin{aligned} \frac{\partial L}{\partial W_{hx}}&=\sum_{t=1}^Tprod(\frac{\partial L}{\partial h_t}, \frac{\partial h_t}{\partial W_{hx}})\\ &=(\sum_{i=t}^T\frac{2}{T}(o_{T+t-i}-y_{T+t-i})^{transpose}W_{oh}W_{hh}^{T-i})^{transpose}x_t^{transpose}\\ &=\sum_{i=t}^T\frac{2}{T}(W_{hh}^{transpose})^{T-i}W_{oh}^{transpose}(o_{T+t-i}-y_{T+t-i})x_t^{transpose} \end{aligned} \]

\[ \begin{aligned} \frac{\partial L}{\partial W_{hh}}&=\sum_{t=1}^Tprod(\frac{\partial L}{\partial h_t}, \frac{\partial h_t}{\partial W_{hh}})\\ &=(\sum_{i=t}^T\frac{2}{T}(o_{T+t-i}-y_{T+t-i})^{transpose}W_{oh}W_{hh}^{T-i})^{transpose}h_{t-1}^{transpose}\\ &=\sum_{i=t}^T\frac{2}{T}(W_{hh}^{transpose})^{T-i}W_{oh}^{transpose}(o_{T+t-i}-y_{T+t-i})h_{t-1}^{transpose} \end{aligned} \]

就可以得到我們要的來做 gradient descent 了！

1.3 練習題給的想法

最後課本內容留有兩個練習題，其中一題與 power method 有關。這個方法指出，當一個矩陣重複自乘多次後再乘上一個任意初始向量，其結果會趨近於該矩陣主特徵值（最大 eigenvalue）所對應的特徵向量方向。

從我們對梯度的推導可以觀察到類似的現象：隨著時間步長 \(T\) 變大，gradient 中會出現越來越多的 \(W_{hh}^k\) 項。這些項在本質上就像是對 \(W_{hh}\) 做了 power iteration，導致梯度的方向逐漸趨向於 \(W_{hh}^{\top}\) 的主特徵向量。

這會帶來兩個問題：

若 \(W_{hh}\) 的主特徵值大於 1，這些項會快速放大，導致 梯度爆炸；

若特徵值小於 1，則項會快速衰減，導致 梯度消失。

因此，模型參數的更新容易被初始的 \(W_{hh}\) 主導，反而降低了對資料本身的敏感度。這也說明了為什麼在實務中，我們通常會對 BPTT 進行時間步長的截斷，或是改用像 LSTM 或 GRU 這類具 gating 機制的架構，來穩定長期依賴的學習。

這篇筆記先紀錄到這裡。